package com.since.algorithm.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * Created by Sincerity on 2020/5/15.
 * 描述：快速排序
 * {@link #quickSort(int[], int, int)}
 */
class QuickSort {
    public static void main(String[] args) {
//        int[] array = {8, 5, 7, 6, 4, 12};
        int[] array = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            array[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        }
        Date date = new Date();
        SimpleDateFormat dateFormat = new SimpleDateFormat("mm:ss:SSS");
        System.out.println("开始时间:" + dateFormat.format(date));
        quickSort(array, 0, array.length - 1);  //800w大约需时间=1.2s 8000w需要大概12.5s
        Date date2 = new Date();
        System.out.println("结束时间:" + dateFormat.format(date2));
    }

    /**
     * 快速排序思路:
     * 1.把待排序数组分成二部分 左边和右边, 左右双指针,左边的数和中轴数对比 左边[i]数小于中轴数 i++ 右边的数大于中轴数 r++
     * 2.如果左边的数array[i]大于中轴数 或者右边的数小于中轴数 将左边的数和右边的数位置调换
     * 3.如果左边的数=中轴数 右边的索引-1  右边的数=中轴数 左边索引+1
     * 4.左边索引等于右边的索引 左边+1 右边-1
     * 5.上述步骤结束后 得到左和右的索引 如果右边的索引>0 从0到左边的索引位置开始递归
     * 6. 如果左边的索引小于数组的长度 从左边索引位置到数组的长度开始递归
     *
     * @param array 目标数组
     * @param left  左边索引
     * @param right 右边索引
     */
    public static void quickSort(int[] array, int left, int right) {
        int l = left, r = right;
        int pivot = array[(l + r) / 2]; //中轴数
        int temp; //用于交换位置
        //把比array[pivot]小的数字放到左边, 大的放到右边
        while (l < r) {

            while (array[l] < pivot) {
                l++;
            }
            while (array[r] > pivot) {
                r--;
            }
            if (l >= r) {
                break;
            }
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            if (array[l] == pivot) r--;
            if (array[r] == pivot) l++;
        }
        //如果 l ==r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l++;
            r--;
        }
        //向左递归
        if (left < r) {
            quickSort(array, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(array, l, right);
        }

    }

}
